public class Main {


    /**
     * 柠檬水找零
     */
    /*class Solution {
        public boolean lemonadeChange(int[] bills) {
            //统计5 10 个数 20 不用统计因为 20 找不出去
            int five = 0;
            int ten = 0;
            for (int x : bills) {
                if (x == 5) {
                    //5就直接收下
                    five++;
                } else if (x == 10) {
                    //10的话就需要先判断是否有5 如果没有直接false 有five-- 10 收下ten++
                    if (five == 0) return false;
                    five--;
                    ten++;
                } else {
                    //20 采用保5 去 10 策略---贪心策略
                    if (ten != 0 && five != 0) {
                        //可贪
                        ten--;
                        five--;
                    } else {
                        //退而求其次--不具备贪的条件
                        if (five >= 3) {
                            five -= 3;
                        } else {
                            return false;
                        }
                    }

                }
            }
            return true;
        }
    }*/

    /**
     * 将数组和减少一半的最少操作次数
     */
    /*class Solution {
        public int halveArray(int[] nums) {
            PriorityQueue<Double> heap = new PriorityQueue<>((a,b) -> b.compareTo(a) );//大根堆
            Double sum = 0.0;
            for(int x : nums) {
                sum += x;
                heap.offer(x / 1.0);
            }
            sum /= 2.0;//得到一半的sum
            int count = 0;//统计操作次数
            //持续的将堆顶元素 也就是数组中最大的元素减半, 直到sum <= sum/2
            while(sum > 0) {
                Double t = heap.poll() / 2.0;
                sum -= t;
                count++;
                heap.offer(t);
            }
            return count;
        }
    }*/


    /**
     * 最大数
      */
    /*class Solution {
        public String largestNumber(int[] nums) {
            //优化: 将每个数转成字符串, 待会组数时就直接拼接, 然后比较字符串字典序即可
            int n = nums.length;
            String[] strs = new String[n];
            for(int i = 0; i < n; i++) {
                strs[i] = "" + nums[i];
            }

            Arrays.sort(strs, (a,b) ->(b+a).compareTo(a + b));
            //返回值
            StringBuffer ret = new StringBuffer();
            for(String s : strs) ret.append(s);
            if(ret.charAt(0) == '0') return "0";//小细节---如果题目给的是{0,0} 则这里需要将前岛零给去掉
            return ret.toString();
        }
    }*/

    /**
     * 摆动序列
     * 思路: 贪心所有的 极点 + 起点 + 终点
     * 遇到平线直接跳过, 取最右端的 也就是单调性出现变化的点
     */
    /*class Solution {
        int left;
        public int wiggleMaxLength(int[] nums) {
            int n = nums.length;
            left = 0;
            int ret = 0;
            for(int i = 0; i <n; i++) {
                if(i == n - 1) {
                    ret++;
                    continue;
                }
                int right = nums[i + 1] - nums[i];//判断i点右边的单调性
                if(right == 0) {
                    //说明当前是水平线
                    continue;
                }
                if(left * right <= 0) {
                    //两者互为相反数---有极点出现
                    ret++;
                    left = right;
                }
            }
            return ret;
        }
    }*/

    /**
     * 最长递增子序列
     */
    /*class Solution {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            ArrayList<Integer> list = new ArrayList<>();
            list.add(nums[0]);
            for(int i = 1; i < n; i++) {
                if(nums[i] > list.get(list.size() - 1) ) {
                    //特别大的一个数
                    list.add(nums[i]);
                }else {
                    //二分查找合适的插入位置
                    int left = 0;
                    int right = list.size() - 1;
                    while(left < right) {
                        int mid = (left + right) / 2;
                        if(list.get(mid) < nums[i] ) {
                            //右边
                            left = mid + 1;
                        }else{
                            right = mid;
                        }
                    }
                    list.set(left, nums[i]);//此处的修改操作就是贪心的, 因为比 7 大的 数一定 比 3 大, 如果原本是7 现在来了个 3
                    // 那么这个3 完全是可以将 7 覆盖掉的, 而且不会有什么 影响
                }
            }
            return list.size();
        }
    }*/

    /**
     * 三元递增序列
     */
   /* class Solution {
        public boolean increasingTriplet(int[] nums) {
            int n = nums.length;
            ArrayList<Integer> ret = new ArrayList<>();
            ret.add(nums[0]);
            for(int i = 1; i < n; i++) {
                if(ret.get(ret.size() - 1) < nums[i]) {
                    ret.add(nums[i]);
                    if(ret.size() == 3) return true;
                    continue;
                }
                //寻找合适的插入位置
                for(int j = 0; j < ret.size(); j++) {
                    if(ret.get(j) >= nums[i]) {
                        ret.set(j, nums[i]);
                        break;
                    }else {
                        continue;
                    }
                }
            }
            if(ret.size() >= 3) return true;
            else return false;
        }
    }
*/

    /*class Solution {
        public boolean increasingTriplet(int[] nums) {
            int a = nums[0], b = Integer.MAX_VALUE;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > b) return true;
                else if (nums[i] <= a) a = nums[i];
                else b = nums[i];
            }
            return false;

        }

    }*/

    /**
     * 最长连续递增子序列
     */
    class Solution {
        public int findLengthOfLCIS(int[] nums) {
            //双指针 + 贪心
            int ret = 1;
            int n = nums.length;
            if(n ==1) return 1;
            int i = 0;
            for(int j  = 1; j < n; j++) {
                if(nums[j] > nums[j - 1]){
                    ret = Math.max(ret, j - i + 1);
                }
                else {
                    //开始贪心
                    i = j;
                }
            }
            return ret;
        }
    }







}
